package heap;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangfeng
 * @date 2019/02/13
 */
public class MaxHeap<T extends Comparable<T>> {

    private List<T> mHeap;

    public MaxHeap(){
        this.mHeap = new ArrayList<>();
    }

    /**最大堆的向下算法
     * 数组实现的堆中，第N个节点的左孩子的索引的值是（2N+1），右孩子的索引是（2N+2）
     * @param start 被下调节点的起始位置（一般为0，表示从第1个开始）
     * @param end 截至范围（一般为数组中最后一个元素的索引）
     */
    protected void filterdown(int start,int end){
       int c = start;
       int l = 2*c+1;
       T tmp = mHeap.get(c);
       while(l<=end){
           int cmp = mHeap.get(l).compareTo(mHeap.get(l+1));
           //l是左孩子，l+1是右孩子
           if(l<end&&cmp<0){
               l++;
           }
           cmp = tmp.compareTo(mHeap.get(l));
           if(cmp>=0)
               break;
           else {
               mHeap.set(c, mHeap.get(l));
               c = l;
               l = 2*l+1;
           }
       }
        mHeap.set(c,tmp);
    }


    protected void filterup(int start){
        int c = start;
        int p = (c-1)/2;
        T tmp = mHeap.get(c);
        while(c>0){
            int cmp = mHeap.get(p).compareTo(tmp);
            if(cmp>=0)
                break;
            else{
                mHeap.set(c,mHeap.get(p));
                c = p;
                p = (p-1)/2;
            }
        }
        mHeap.set(c,tmp);
    }

    /**
     * @param data
     * @return
     */
    public int remove(T data){
     return 0;
    }
}
